from typing import *
from itertools import accumulate


class Solution:
    def maxFreeTime(
        self, eventTime: int, k: int, startTime: List[int], endTime: List[int]
    ) -> int:
        n = len(startTime)
        a = [0] * n
        for i, (s, e) in enumerate(zip(startTime, endTime)):
            a[i] = e - s
        b = list(accumulate(a, initial=0))
        ans = 0
        for i in range(k - 1, n):
            l = i - k + 1
            L = endTime[l - 1] if l - 1 >= 0 else 0
            R = startTime[i + 1] if i + 1 < n else eventTime
            ans = max(ans, R - L - (b[i + 1] - b[i + 1 - k]))
        return ans


class Solution:
    def maxFreeTime(
        self, eventTime: int, k: int, startTime: List[int], endTime: List[int]
    ) -> int:
        n = len(startTime)
        a = [e - s for s, e in zip(startTime, endTime)]
        b = list(accumulate(a, initial=0))
        ans = 0
        for i in range(k - 1, n):
            L = endTime[i - k] if i - k >= 0 else 0  # l = i - k + 1
            R = startTime[i + 1] if i + 1 < n else eventTime
            ans = max(ans, R - L - (b[i + 1] - b[i + 1 - k]))
        return ans


s = Solution()
print(s.maxFreeTime(eventTime=5, k=1, startTime=[1, 3], endTime=[2, 5]))
print(s.maxFreeTime(eventTime=10, k=1, startTime=[0, 2, 9], endTime=[1, 4, 10]))
print(
    s.maxFreeTime(eventTime=5, k=2, startTime=[0, 1, 2, 3, 4], endTime=[1, 2, 3, 4, 5])
)
